package algorithmic_data_structure.bfprt;

// 前面三步看作bfprt
//1. 分组(5个一组) 2. 排序（五个元素进行排序O(N),这里选择的是插入排序，为什么是O(N)呢？你可以把5个当作一个，每5个元素排序可以看作常熟时间，加起来就是O(N)）
//3. 取出分组的中位数组成数组m 4. 对m递归执行bfprt选出 中位数p（分界值）
//5. 用p进行分界 6. 查看第k小的值是否在p中，不在就继续递归

// 时间 复杂度 固定 为 O（N）
// 为什么5个数一组，似乎是因为5个人想出来这个算法，所以。。。
// 可以稳定的淘汰一批数（每次3N/10）
public class 手写bfprt {
    // 利用bfprt算法求解，是O(N)的过程
    public static int getMinKthByBFPTR(int[] arr, int K) {
    	return select(arr, 0, arr.length - 1, K - 1);
    }
    //看作黑盒，求出数组arr 在 [begin,end]中第k大的元素
    public static int select(int[] arr, int begin, int end, int k) {
    	if (begin == end) {//数组中只有一个数时，直接返回
    		return arr[begin];
    	}
    	int pivot = medianOfMedians(arr, begin, end);//求出以哪个数作为划分值
		//注意，进行完partation过程后，arr数组已经不是无序的了，而是以P作为分界的两部分
    	int[] pivotRange = partition(arr, begin, end, pivot);//返回的是分界p所在的领域左右下标
    	if (k >= pivotRange[0] && k <= pivotRange[1]) {
    		return arr[k];//如果需要求的数正好在等于区域，直接返回arr[k]
    	} else if (k < pivotRange[0]) {//此时我们要找的数比divide小，递归求前半部分
    		return select(arr, begin, pivotRange[0] - 1, k);
    	} else {//此时我们要找的数比divide大，递归求后半部分
    		return select(arr, pivotRange[1] + 1, end, k);
    	}
    }
    //这个函数是将root数组star位置到finish位置分成每5个数一个小组，并求出每个小组内的中位数
    public static int medianOfMedians(int[] arr, int begin, int end) {
    	int num = end - begin + 1;//求出长度
    	int offset = num % 5 == 0 ? 0 : 1;//最后如果剩余的数不足5个，我们也将其分成一个小组，和前面同等对待
    	int[] mArr = new int[num / 5 + offset];//这个数组存的是每个小组内的中位数
    	for (int i = 0; i < mArr.length; i++) {//依次往median数组中填数
    		int beginI = begin + i * 5;//第i组数对应root数组上的位置
    		int endI = beginI + 4;
    		mArr[i] = getMedian(arr, beginI, Math.min(end, endI));
    	}
    	//求出生成好的median数组的中位数，作为partation函数的划分值
    	return select(mArr, 0, mArr.length - 1, mArr.length / 2);
    }
    //这个函数求的是在root数组中beginI位置到endI位置上的中位数（其实就是求由每5个数所分成的小组的小组内的中位数）
    public static int getMedian(int[] arr, int begin, int end) {
    	//插入排序
    	insertionSort(arr, begin, end);
    	int sum = end + begin;
    	int mid = (sum / 2) + (sum % 2);//这个地方加上sum%2是为了确保偶数个数时我们求的是中间两个数的后一个
    	return arr[mid];
    }
    public static void insertionSort(int[] arr, int begin, int end) {
    	for (int i = begin + 1; i != end + 1; i++) {
    		for (int j = i; j != begin; j--) {
    			if (arr[j - 1] > arr[j]) {
    				swap(arr, j - 1, j);
    			} else {
    				break;
    			}
    		}
    	}
    }

    //partation函数求的是等于pivotValue的范围, 在 arr【range[0]~range[1]】 中 都是 等于 pivotValue
    //同时也会把数组按pivotValue 分成左右两部分
    public static int[] partition(int[] arr, int begin, int end, int pivotValue) {
    	int small = begin - 1;//这么设值是为了应对整个数组都是比pivotValue大的情况，尽管概率很小
    	int cur = begin;
    	int big = end + 1;//这么设值是为了应对整个数组都是比pivotValue小的情况，尽管概率很小
    	while (cur != big) {
    		if (arr[cur] < pivotValue) {
    			swap(arr, ++small, cur++);
    		} else if (arr[cur] > pivotValue) {
    			swap(arr, cur, --big);
    		} else {
    			cur++;
    		}
    	}
    	int[] range = new int[2];
    	range[0] = small + 1;
    	range[1] = big - 1;
    	return range;
    }
    public static void swap(int[] arr, int index1, int index2) {
    	int tmp = arr[index1];
    	arr[index1] = arr[index2];
    	arr[index2] = tmp;
    }
}
